JPEG 2000 relates to an image coding. The image format is described in ISO document 15444-1. The JPEG 2000 format is designed to compactly represent an image while allowing convenient manipulation and selective access.
A significant drawback of the JPEG 2000 format is its computational complexity, which far exceeds that of earlier formats such as original JPEG. This computational complexity results in a large increase in the time required to translate an image to or from JPEG 2000 format by software running on a general-purpose computer. Major steps typically comprising the translation of an un-encoded image to JPEG 2000 format are the following:                1) A color-component transform;        2) A wavelet transform;        3) Quantization;        4) Coefficient bit modeling;        5) Entropy coding.        
Translation of an image from JPEG 2000 format to an un-encoded format normally comprises the same steps in reverse order. Of these, Step (4) (Coefficient bit modeling) is by far the most complex of the mentioned operations and is the subject of this invention.
JPEG 2000's coefficient bit modeling is described in Annex D of ISO 15444-1. Its description requires some limited familiarity with the preceding and succeeding steps.
In translating an image to JPEG 2000 format, e.g., during JPEG 2000 encoding the steps (color-component transform, wavelet transform, and quantization) preceding the coefficient bit modeling step generate a set of coefficient indices—often numbering a million or more—describing the image. These indices are partitioned into units called code-blocks. Each code-block comprises a rectangular array of coefficient indices. The coefficient indices of a single code-block all belong to a single contiguous subrectangle of the image, all belong to a single color component generated by the color-component transform, and all belong to a single frequency sub-band generated by the wavelet transform. This sub-band (and hence the corresponding code-block) corresponds to one of four specific types “flavors” (LL, LH, HL, or HH) according to the formulae with which it is generated by the wavelet transform. LL corresponds to a Low-pass horizontal, Low-pass vertical sub-band. LH corresponds to a Low-pass horizontal, High-pass vertical sub-band. HL corresponds to a High-pass horizontal, Low-pass vertical sub-band. HH corresponds to a High-pass horizontal, High-pass vertical sub-band.
In JPEG 2000 each coefficient index is most usefully considered in sign-magnitude (base-2) representation. The magnitude is represented by a sequence of binary symbols (bits) ranging from the most significant (leftmost) to the least significant (rightmost). The more zero-valued leftmost bits in the representation, the smaller the magnitude value; if all bits are zero-valued, the coefficient index has the value zero. An additional bit indicates whether the coefficient index is positive or negative—value 0 for a positive coefficient index and value 1 for a negative. This sign bit is ignored if the magnitude is zero.
Entropy-coding which follows the coefficient bit modeling step in JPEG 2000 encoding encodes the bit values of the coefficient indices using a specific coding algorithm called the MQ-coder. The MQ-coder is one of a family of algorithms which attempt to predict each bit-value based on the previous history of coded bit-values. When the prediction is correct, the bit-value is coded more compactly—the more confident the original prediction, the more compact the resulting coding. Conversely, when the prediction is incorrect, the bit-value must be coded using more than one bit—and the more confident the original prediction, the greater the penalty for an incorrect guess. However, the trade-off is such that the more confident the prediction, the more compact the overall coding is, even taking into account the penalty for mistaken predictions.
Let P be a value between 0.5 and 1 indicating the confidence of a given bit-value prediction. Values of P less than 0.5 do not occur because such would indicate that the opposite bit-value is more likely to occur. A value of P equaling 1 indicates perfect confidence—a predicted value that is guaranteed to be correct. The number of bits required to code the bit-value in the event the prediction is correct is given by (lg P) (base 0.5 logarithm of P). The number of bits required to code the bit-value in the event the prediction is incorrect is given by (lg(1−P)). Taking probabilities of both correct and incorrect prediction into account, the overall expected number of bits required to code the bit-value is H=(P lg P+(1−P)lg(1−P)). Table 1 shown below shows the bits required to code correct and incorrect predictions, and the overall expected number of bits required, for various sample values of P.
TABLE 1Plg Plg(1 − P)H0.51.00001.00001.00000.60.86561.32190.97100.70.51461.73700.88130.80.32192.32190.72190.90.15203.32190.46901.00.0000infinity0.0000
The compactness of the coding is greatly enhanced by grouping the bit-values to be coded into categories. The bit-values in each category are expected to have similar confidence values of predictability. This grouping should be done on the basis of preceding bit-values in the code-stream, so that it can be performed in the same manner whether translating to or from JPEG 2000 format. The information from the preceding code-stream bit-values used to categorize a given bit-value is called the context for that bit-value.
In order that a MQ-coder be able to encode (or decode) coefficient index bit-values generated by Steps (1)-(3), those bit-values must be ordered in a certain sequence and each bit-value must be categorized. This is the “coefficient bit modeling” task identified as Step (4).
An overview of coefficient bit modeling will now be presented. Each code-block can be considered as an independent unit. This is the JPEG 2000's standard approach. When translating (encoding) to JPEG 2000 format, each code-block is modeled and coded independently, and the various code-streams are then interleaved, e.g. using known methods. When translating from JPEG 2000 format, the code-streams for the various code-blocks are first de-interleaved and each code-block is then independently decoded.
Within a single code-block, the bit-values are organized into bit-planes according to position. The leftmost bit-plane includes the leftmost bit-values for all coefficient indices, the next bit-plane includes the next bit-values for all coefficient indices, and so on, the rightmost bit-plane includes the rightmost bit-values for all coefficient indices. The sign-bits for all coefficient indices do not form a bit-plane but are coded at various locations in the code-stream depending on the various coefficient index values. As a general principle all bit-values for a given bit-plane are coded before any bit-values of the next bit-plane to the right. However, bit-values within a single bit-plane are ordered in an intricate and not easily predictable sequence, according to JPEG 2000 encoding principles which will be described below.
Some bit-values (those considered to have the least impact on image quality) may actually be left uncoded. If any bit-values of a given bit-plane are left uncoded, then all bit-values of any bit-planes further right are uncoded. The JPEG 2000 coding process will now be described under the assumption that all bit-values are coded
Recall that the coefficient indices for a given code-block form a rectangular array. Thus surrounding a typical coefficient index are eight immediate neighbors (nine if the coefficient index itself is counted), those coefficient indices immediately adjacent both horizontally and vertically. The exceptions are coefficient indices at the boundary of the code-block, which may have only five or three immediate neighbors. The location of a bit-value in the code-stream for its bit-plane and the context used by the MQ-coder for coding the bit-value are derived from the values of these neighbors. “Missing” neighbors of coefficient indices at the boundary or corners of the code-block are treated as if zero-valued for the purpose of coefficient bit modeling.
Of particular importance is the significance state of the neighboring coefficient indices: a value 0 or 1 indicating whether the coefficient index is known to be non-zero based on previously coded information. In the course of coding a given bit-plane, any coefficient index having a non-zero bit-value in any previously coded bit-plane has a significance state of 1; any coefficient index having zero bit-values in all bit-planes up to and including the current bit-plane has a significance state of 0. A coefficient index having zero bit-values in all preceding bit-planes and a non-zero bit-value in the current bit-plane may have a significance state of 0 or 1, depending on whether that coefficient's bit-value for the current bit-plane has already been coded (1) or not (0).
Coefficient indices with a significance state of 1 are called significant; those with a significance state of 0 are called insignificant. The status of a coefficient index as significant or insignificant may change as coding progresses. All coefficient indices in JPEG 2000 are insignificant at the start of coding; some switch from insignificant to significant in the course of coding, but no coefficient ever switches from significant to insignificant.
Each bit-plane of the code-block is coded in three coding passes. Each coding pass follows a known scanning pattern. The code-block's coefficient indices are partitioned horizontally into stripes, each stripe includes four rows (except that the bottommost stripe comprises one to four rows depending on the code-block height). Each stripe is partitioned vertically into columns each containing four coefficient indices except that each column of the bottommost stripe contains as many coefficient indices as the number of rows in the stripe. In each coding pass, bit-values of each stripe are coded before the stripes below; within each stripe, bit-values of each column are coded before columns to the right; and within each column, bit-values are coded from top to bottom. In any coding pass some or all bit-values may be skipped, but those values not skipped are coded in the sequence given by this scanning pattern. Each bit-value of each bit-plane is coded in exactly one of the three coding passes (and therefore skipped in the other two coding passes) for that bit-plane.
The JPEG 2000 significance-propagation pass is the first of three different types of coding passes for a given bit-plane which are performed as part of the JPEG 2000 coefficient bit modeling step. In the significance-propagation pass, bit-values are coded for those coefficient indices which:                1) are not significant before the current coding pass; and        2) have at least one significant neighbor at the time the given bit-value is coded.Note that due to condition (2), the particular specified scanning pattern influences the inclusion of bit-values in the significance-propagation pass. The choice of MQ-coder context for each bit-value is determined by the significance state of the given coefficient index's eight neighbors. In the present application we let Csp denote the configuration of the eight neighbors' significance states. Since each significance state has two possible values, the possible number of such configurations is 28=256.        
The JPEG 2000 Specification stipulates that the MQ-coder context value, Msp, used to code the current bit-value, taking one of nine possible values arbitrarily labeled S0-S8, be derived from the configuration value by an ad hoc correspondence Asp: Msp =Asp(Csp). (In a special case, the context value S0, indicates that all eight neighbors are insignificant and that the given bit-value is not coded in the significance-propagation pass.) If performed by logical operations, as done in some systems, determining Asp represents a considerable computational burden. The details of the ad hoc correspondence depends on whether the code-block being coded is of type LL, LH, HL, or HH. The rules for each are summarized in Tables 2 and 3 shown below, in terms of the total number H=0, 1, or 2 of significant horizontal neighbors, the total number V=0, 1, or 2 of significant vertical neighbors, and the total number D=0, 1, 2, 3, or 4 of significant diagonal neighbors. Every possible configuration Csp is found in one row of the table.
TABLE 2MQ-coder contexts for LL or LH code-blocksMspHVDS0000S1001S200at least 2S301anythingS402anythingS5100S610at least 1S71at least 1anythingS82anythinganything
TABLE 3MQ-coder contexts for HH code-blocksMspH + VDS000S110S2at least 20S301S411S5at least 21S602S7at least 12S8anythingat least 3
The ad hoc correspondence for HL blocks is identical to that for LL or LH blocks except that the role of H and V are reversed.
Each bit-value coded in the significance-propagation pass of JPEG 2000 coding is coded using the corresponding context value Msp. If the coded bit-value is 0, the given coefficient index has not yet become significant (blossomed in our terminology used in the present application) and is ignored until the next bit-plane is coded.
If the coded bit-value is 1, the given coefficient has just blossomed. The sign bit for the given coefficient index is coded immediately thereafter. This coding operation also requires determination of a context. The sign-bit context is determined from a configuration Csb corresponding to the significance states and the signs, if significant, of the four immediate neighbors (located immediately above, below, right, or left of—but not diagonally offset from—the given coefficient being coded. Since each of the four immediate neighbors has three possible states (insignificant, significant and positive, or significant and negative), the number of such possible configurations is 34=81. The JPEG 2000 Specification stipulates that the MQ-coder context value, Msb, used to code the sign bit, take one of five MQ possible values arbitrarily labeled S9-S13 that can be determined from the configuration value Csb by an ad hoc correspondence Asb: Msb=Asb(Csb). In addition, a default sign-bit value Dsb is derived from Csb by an ad hoc correspondence Bsb: Dsb=Bsb(Csb). Once again, the evaluation of Asb(Csb) and Bsb(Csb), if performed in known JPEG 2000 implementations by logical operations, is a significant computational burden.
Details of the ad hoc correspondence used to calculate Msb and the default sign bit Dsb are given in Table 4 shown below in terms of the total number H+=0, 1, or 2 of positive significant horizontal neighbors, the total number H−=0, 1, or 2 of negative significant horizontal neighbors, the total number V+=0, 1, or 2 of positive significant vertical neighbors, and the total number V−=0, 1, or 2 of negative significant vertical neighbors. This correspondence is the same for LL, LH, HL, or HH code-blocks.
TABLE 4MsbDsb(H+) − (H−)(V+) − (V−)S9+00S10+0positiveS10−0negativeS11+positivenegativeS11−negativepositiveS12+positive0S12−negative0S13+positivepositiveS13−negativenegativeNote that MQ-coder context S9 is used only with default sign-bit value +.
The major computational tasks in the significance-propagation pass are:                1) Determining whether each bit-value of the current bit-plane is coded in the significance-propagation pass;        2) Assembling the neighborhood configurations Csp and Csb; and        3) Evaluating the coding contexts Asp(Csp) and Asb(Csb) and the default sign-bit value Bsb(Csb).        
Depending on the method of implementation, these tasks may overlap and, in most implementations, involve a large number of computations.
The second of the three JPEG 2000 coding passes for a given bit-plane is the magnitude-refinement pass. This coding pass will now be discussed. In the magnitude-refinement pass, bit-values are coded for those coefficient indices which:                1) became significant before the current bit-plane.        
This condition is independent of the particular specified scanning pattern. The choice of MQ-coder context used for each bit-value is determined by the significance state of the given coefficient index's eight neighbors, and on whether the coefficient became significant with the immediately preceding bit-plane or earlier. We let Cmr denote the configuration of the eight neighbors' significance states. The possible number of such configurations is 2×28=512.
The JPEG 2000 Specification stipulates that the MQ-coder context value, Mmr, used to code the current bit-value, take one of three possible values arbitrarily labeled S14-S16 and that it be derived from the configuration value by an ad hoc correspondence Amr: Mmr=Amr(Cmr). This correspondence is considerably simpler than the previously mentioned Asp, Asb, and Bsb relationships, but still represents a nontrivial computational burden.
Major computational tasks in the magnitude-refinement pass include:                1) Determining whether each bit-value of the current bit-plane is coded in the magnitude-refinement pass;        2) Assembling the neighborhood configuration Cmr; and        3) Evaluating the coding context Amr(Cmr).        
The third of JPEG-2000's three coding passes for a given bit-plane is the clean-up pass. The clean-up pass will now be discussed. In the clean-up pass, bit-values are coded for those coefficient indices which were not coded in the significance-propagation or magnitude-refinement passes. Note that all such coefficients must be insignificant.
The choice of MQ-coder context for coding each bit-value and the sign bit-values of blossoming coefficients are determined in the same way as in the significance-propagation pass, using the neighborhood configurations Csp and Csb and the correspondences Asp and Asb. One important difference is that the bit-value is coded even if the MQ-coder context Asp(Csp) equals S0. All bit-values coded in the clean-up pass had values of S0 for Msp in the preceding significance-propagation pass; the value of Msp now differs if any neighboring coefficients became significant since the previous calculation.
Once again, the evaluation of Asp(Csp), Asb(Csb) and Bsb(Csb), if performed by logical operations as in known systems, is a significant computational burden.
The clean-up pass manifests an additional complication beyond the significance-propagation pass. In the case that all four coefficients of a column are insignificant and to be coded in the clean-up pass, and all fourteen neighboring coefficients of the column are insignificant, a special run-length code is used to indicate the number 0, 1, 2, 3, or 4 of zero bit-values from the top of the column downwards. The code has one or three bits, interpreted as in Table 5 shown below.
TABLE 5number ofcodeleading zeroes041113110210111000
If the number of leading zeros is less than four (thus comprising less than the entire column) the first bit-value following is known to be 1. Calculation of Csp and Msp and the coding of this bit-value may therefore be omitted, but Csb, Msb, and Dsb must still be calculated and the sign bit decoded. For any subsequent bit-values in the column, both the bit-value and (if applicable) the sign bit must be coded, entailing the usual calculation of Csp, Msp, Csb, Msb, and Dsb. (Run-length coding is not used for columns containing fewer than four coefficients.) This run-length coding format enables a particular known rapid coding method, for one or several columns consisting entirely of zeros.
The major computational tasks in the JPEG-2000 coding clean-up pass are:                1) Determining whether each bit-value of the current bit-plane is coded in the clean-up pass;        2) Assembling the neighborhood configurations Csp and Csb; and        3) Evaluating the coding contexts Asp(Csp) and Asb(Csb) and the default sign-bit value Bsb(Csb).        
Frequently one or several leading bit-planes for a code-block consist entirely of zeroes. All coefficients for a code-block are insignificant until a bit-value 1 is encountered. Note that for leading zero bit-planes no bit-values are code in the significance-propagation or clean-up passes. Effectively the first bit-plane coded for a code-block involves only the clean-up pass since no changes are made during the significance propagation and magnitude refinement pass performed on the first bit plane. The JPEG 2000 Specification allows leading zero bit-planes to be skipped in coding, but also permits such bit-planes to be explicitly coded.
In lossy image coding, some bit-values are typically left uncoded. In many cases, this is done by omitting one or more trailing coding passes in their entirety. This normally has no effect on the choice of bit-values to be coded and calculation of MQ-coder contexts described above.
Various principles of fast software execution that can be relevant to JPEG 2000 coding implementations will now be discussed. The computational complexity of JPEG 2000's coefficient bit modeling makes ways of providing rapid execution of JPEG 2000 encoding routines desirable. Instruction pipelining and parallelism is one way of facilitating rapid software execution. Even an ostensibly serial-execution microprocessor such as a Pentium manifests a significant degree of parallelism in instruction execution—parallelism profitably enhanced by careful code design. Execution of a single microprocessor operation such as an addition entails performance of several sub-tasks. The instruction itself must be fetched from memory, then interpreted. Perhaps one of the argument values must be again fetched from memory before the operation is actually performed. In order to execute a sequence of operations O1, O2, O3, . . . quickly, the processor “pipelines” the processing. For example, while operation O1 is actually being executed, simultaneously the argument value for operation O2 may be fetched from memory, operation O3 may be in the process of interpretation, and operation O4 may be fetched from memory. The details of this pipelining vary from one processor to another, but the basic principle is widespread.
Many modern microprocessors go even further by parallelizing execution, for example perhaps simultaneously executing operations O1 and O2, fetching arguments for operations O3 and O4, interpreting operations O5 and O6, and fetching operations O7 and O8. This parallelization is subject, however, to an important constraint. Operations O1 and O2 cannot be executed simultaneously if both must modify the same register or memory location (such a pair of operations is inherently sequential in nature). Careful code design, minimizing the immediate adjacency of such pairs of non-parallelizable operations, can theoretically increase execution speed by a factor of two over the worst case.
Pipelining of operations requires special finesse in the event that the program “branches”, i.e., transfers control to a non-contiguous location in memory. Branches are a necessary feature for program loops and conditional execution and appear frequently in any but the most straightforward and uncomplicated programs.
A branch complicates the pipelining of operations because the operation to be executed two steps after operation O1 may not be the nearby operation O3 but an operation O100 at some distant memory location. It is therefore useless for the processor to interpret operation O3 simultaneously with the execution of O1. Microprocessors have grown increasingly sophisticated in their ability to pipeline operations separated by branches, but this sophistication entails unintended and undesired consequences if not accounted for in program design.
A program branch may be conditional or unconditional. An unconditional branch is simply a transfer of control which happens identically regardless of conditions. The unconditional branch is the easiest and was the earliest to be reconciled with instruction pipelining; the instructions fed into the pipeline are simply taken from the far end of the branch rather than immediately subsequent locations in memory.
A conditional branch may or may not take place depending on processor status when the branch instruction is reached. For example, the branch may or may not be executed depending on whether the result of the immediately preceding operation was positive, or negative, or an overflow. Conditional branches are difficult to reconcile with instructions to be pipelined because which of two possible locations the next instruction to be fed to the pipeline is located is impossible to predict given the information available at the time the instruction is fed.
The approach taken is to attempt to predict whether the branch will be taken based on previous history executing the same body of code. The details of the method used to make this prediction vary from one processor to another and are of little importance; the important point is that when the prediction is correct there is no interruption to the instruction pipeline. On the other hand, an incorrect prediction may, and often does entail a large time penalty.
Branch prediction is of greatest benefit when applied to a branch such as the end of a loop, which may be taken many times (once for each execution of the loop) and declined only once (when exiting the loop). The large time penalty for the final, incorrect prediction is thus offset by the many correct predictions which avoided interruption of the instruction pipeline.
Branch prediction is most problematic for a conditional branch which is repeatedly both taken and declined on an unpredictable basis.
Memory caching can also be used to facilitate fast software execution. Another feature of modern microprocessors is the use of a modest-size memory cache incorporated into the processor for rapid access to frequently used data. Blocks of memory (of a certain size dependent on the type of processor) are loaded into the cache as part of the block is accessed. This initial loading is a slow operation, but subsequent access of the same block is very fast. A well-designed program therefore refrains from repeatedly accessing memory in many widely dispersed locations in a limited time, as such would require different memory blocks to be repeated loaded into the cache with the associated delays.
Image encoding has found many applications and is often implemented using personal computers, workstations and/or other general purpose types of computers. In view of the above discussion, it should be appreciated that JPEG 2000 image encoding can be a very computationally complex. It should also be appreciated that methods of performing JPEG 2000 encoding in a relatively efficient manner that can be implemented using conventional general purpose computer systems, dedicated hardware or a combination of a general purpose computer and some dedicated hardware would be desirable. Preferably at least some methods should be capable of supporting relatively fast encoding of images.